前言:

大家好，第一次發文往後請各位前輩多多指教，我文筆很糟，有手殘的地方請見諒。
首先先感謝朋友介紹Google Code Jam這活動，但錯過了沒機會參加到，還好Google還是開放讓人做題目，直接奉上題目網址了。
原題目

題目:

有個外星機器人使用指令來進行攻擊，預設攻擊為1，幸運的是我們知道他所擁有的指令為以下兩種：

• C (for "charge"): 使光束攻擊加倍。
• S (for "shoot"): 射擊光束，傷害等於目前"charge"的傷害。
  範例，假如目前機器人的指令是SCCSSC，則機器人在執行時的動作為：
• 射擊光束，造成1點傷害。
• 使光束傷害翻倍到2。
• 使光束傷害翻倍到4。
• 射擊光束，造成4點傷害。
• 射擊光束，造成4點傷害。
• 使光束傷害翻倍到8。
  所受的總傷害為9點傷害
  目前已經開發出一種可承受D傷害的盾牌，但機器人目前的程序運行會造成更大傷害。
  宇宙總統攻擊機器人程序，他唯一的攻擊方法就是交換兩個相鄰的指令。
  範例，總統可以交換第三個和第四個指令來破解上面指令SCSCSC，這樣傷害就變為7，然後第四個和第五個可以再交換變成SCSSCC，傷害就降到5，以此類推。
  為了防止機器人懷疑，總統不能破解太多次，請計算出最小破解次數，確保D總傷不大於盾牌。

輸入

輸入第一行T，為測試筆數，每筆包含整數D和一個字串P:盾牌所承受的最大總商和機器人指令。

輸出

輸出每筆資料，包含Case #x: y，其中x是測試筆數編號，y是目標所需最小數量，或是IMPOSSIBLE。

範圍

1 <= Ť <= 100 。
1 <= D <= pow(10,9)。
2 <= P的長度 <=30 。
P的字符是C或S。
時間限制：每個測試集20秒。
記憶體限制：1GB。

範例

輸入:
6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

輸出:
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5

解析:

1. 只有C在S前才必須交換，也就是我們要找到"CS"。
2. 因為次數要求最少，我們就必須從最後面開始找"CS"(後面的S必定大於等於前面效益最大)。
3. 找到後交換(每交換一次次數 + 1)和將目前多餘的攻擊扣除S當時的攻擊除2(因為交換了，少了2被傷害)，反覆直到攻擊小於等於0。

由上面三點我們得知，我們剛開始所需要的資料為，多餘的攻擊、S的位置和S當時的攻擊。

程式碼:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 交換。
template<class T>
void Swap(T& t1, T& t2)
{
	T save = t1;
	t1 = t2;
	t2 = save;
}

// 處理
// command: 指令。(因為會變動到資料所以直接拷貝)
// attakData: 攻擊的位置.目前位置的攻擊。
// needShield: 目前所需要的盾牌量(多出來的攻擊)。
int Process(string command, vector<vector<int>>& attakData, int needShield)
{

	int count = 0;
    
    // 直到我們不需要盾牌。
	while (needShield > 0)
	{
      　for (int index = attakData.size() - 1; index > -1; index--)
		{
            // 得取"S"的索引位置。
			int offset = attakData[index][0];
            
            // 判斷上一個是不是"C"("CS"我們才交換)。
			if (command[offset - 1] == 'C')
			{
                // 交換.更新"S"位置和光束的攻擊大小。
				Swap(command[offset], command[offset - 1]);
				count++;
				attakData[index][0] = offset - 1;
				attakData[index][1] >>= 1;
				needShield -= attakData[index][1];
				break;
			}
		}
	}
	return count;
}

// 設定資料。
// command: 指令。
// attakData: 攻擊的位置.目前位置的攻擊。
// attak: 目前總攻擊。
void SetData(const string& command, vector<vector<int>>& attakData, int& attak)
{
	int base = 1;

	for (size_t index = 0; index < command.length(); index++)
	{
		if (command[index] == 'C')
		{
			base <<= 1;
		}
		else if (command[index] == 'S')
		{
			vector<int> data(2);
			data[0] = index;
			data[1] = base;
			attak += base;
			attakData.push_back(data);
		}
	}
}

// 檢查.初始化所需資料。
// command: 指令。
// shield: 盾牌。
int Compute(string& command, const int shield)
{
    // 等於0為IMPOSSIBLE。
	if (command.length() == 0)
	{
		return -1;
	}
    
    // 得取S的位置.S當下攻擊和目前的總攻擊。
	vector<vector<int>> attakData;
	int attak = 0;
	SetData(command, attakData, attak);
    
    // 攻擊次數大於盾牌為IMPOSSIBLE(都是1也無法抵擋)。
	if (attakData.size() > shield)
	{
		return -1;
	}
    
    // 計算最小需要幾次。
	return Process(command, attakData, attak - shield);
}

// 輸入和輸出。
void Input()
{
	int count = 0;
	int shield = 0;
	string command = "";

	while (cin >> count)
	{
		for (int index = 0; index < count; index++)
		{
			if (cin >> shield >> command)
			{
				int result = Compute(command, shield);
                
				if (result == -1)
				{
					cout << "Case #" << index + 1 << ": " << "IMPOSSIBLE" << endl;
				}
				else
				{
					cout << "Case #" << index + 1 << ": " << result << endl;
				}
			}
		}
	}
}

int main()
{
	Input();
	return 0;
}

結果

註:輸出部分要很注意Case #1 : N，N前面還有一個空格，測了一小時不過就是因為少了空格...。